#include <iostream>
#include <vector>

using namespace std;

class Solution1 {
public:
    vector<vector<int>> res;
    vector<int> path;
    int t, sum;

    void dfs(vector<int>& candidates, int pos)
    {
        if (sum >= t)
        {
            if (sum == t)
                res.push_back(path);
            return;
        }
        for (int i = pos; i < candidates.size(); ++i)
        {
            path.push_back(candidates[i]);
            sum += candidates[i];
            dfs(candidates, i);
            sum -= candidates[i];
            path.pop_back();
            if (sum + candidates[i] >= t) return;
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        t = target, sum = 0;
        dfs(candidates, 0);
        return res;
    }
};

class Solution2 {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(int k, int n, int pos)
    {
        if (k < 0 || n < 0) return;
        if (k == 0 && n == 0)
        {
            res.push_back(path);
            return;
        }

        for (int i = pos; i <= 9; ++i)
        {
            path.push_back(i);
            dfs(k - 1, n - i, i + 1);
            path.pop_back();
            if (n - i < 0) return;
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return res;
    }
};

class Solution3 {
public:

    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };

    int solve(vector<vector<char> >& grid) {
        int res = 0;
        int n = grid.size(); int m = grid[0].size();

        function<void(int, int)> dfs = [&](int i, int j) {
            grid[i][j] = '0';
            for (int k = 0; k < 4; ++k)
            {
                int x = i + dx[k]; int y = j + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1')
                    dfs(x, y);
            }
        };

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == '1')
                {
                    res++;
                    dfs(i, j);
                }
            }
        return res;
    }
};

int main()
{

	return 0;
}